package Tree;

public class leet_124 {
}

class Solution_124 {

    int maxNum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        DFS(root);
        return maxNum;
    }

    /**
     * 遍历出该节点能提供的最大有效路径
     * @param root
     */
    public int DFS(TreeNode root){
        if(root==null){
            return 0;
        }

        // 如果节点发现其有效路径小于0 那代表这条路径加了是在缩减最小值，不能添加
        int left = Math.max(DFS(root.left), 0);
        int right = Math.max(DFS(root.right),0);

        int pathValue = root.val + left + right;

        // 如果发现当前有效路径 比以前的大，更改有效路径最大值
        maxNum = Math.max(pathValue, maxNum);

        // 返回这个有效路径
        return root.val + Math.max(left, right);
    }

}